/*-------------------------------------------------------------------------
 *
 * array_selfuncs.c
 *	  数组运算符选择性估计的函数
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/utils/adt/array_selfuncs.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include <math.h>

#include "access/htup_details.h"
#include "catalog/pg_collation.h"
#include "catalog/pg_operator.h"
#include "catalog/pg_statistic.h"
#include "utils/array.h"
#include "utils/builtins.h"
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"
#include "utils/typcache.h"


/* "@>" 和 "<@" 运算符的默认选择性常数 */
#define DEFAULT_CONTAIN_SEL 0.005

/* "&&" 运算符的默认选择性常数 */
#define DEFAULT_OVERLAP_SEL 0.01

/* 给定运算符的默认选择性 */
#define DEFAULT_SEL(operator) \
	((operator) == OID_ARRAY_OVERLAP_OP ? \
		DEFAULT_OVERLAP_SEL : DEFAULT_CONTAIN_SEL)

static Selectivity fc_calc_arraycontsel(VariableStatData *fc_vardata, Datum fc_constval,
									 Oid fc_elemtype, Oid fc_operator);
static Selectivity fc_mcelem_array_selec(ArrayType *fc_array,
									  TypeCacheEntry *fc_typentry,
									  Datum *fc_mcelem, int fc_nmcelem,
									  float4 *fc_numbers, int fc_nnumbers,
									  float4 *fc_hist, int fc_nhist,
									  Oid fc_operator);
static Selectivity fc_mcelem_array_contain_overlap_selec(Datum *fc_mcelem, int fc_nmcelem,
													  float4 *fc_numbers, int fc_nnumbers,
													  Datum *fc_array_data, int fc_nitems,
													  Oid fc_operator, TypeCacheEntry *fc_typentry);
static Selectivity fc_mcelem_array_contained_selec(Datum *fc_mcelem, int fc_nmcelem,
												float4 *fc_numbers, int fc_nnumbers,
												Datum *fc_array_data, int fc_nitems,
												float4 *fc_hist, int fc_nhist,
												Oid fc_operator, TypeCacheEntry *fc_typentry);
static float *fc_calc_hist(const float4 *fc_hist, int fc_nhist, int fc_n);
static float *fc_calc_distr(const float *fc_p, int fc_n, int fc_m, float fc_rest);
static int	fc_floor_log2(uint32 fc_n);
static bool fc_find_next_mcelem(Datum *fc_mcelem, int fc_nmcelem, Datum fc_value,
							 int *fc_index, TypeCacheEntry *fc_typentry);
static int	fc_element_compare(const void *fc_key1, const void *fc_key2, void *fc_arg);
static int	fc_float_compare_desc(const void *fc_key1, const void *fc_key2);


/*
 * scalararraysel_containment
 *		通过数组包含估计 ScalarArrayOpExpr 的选择性。
 *
 * 如果我们有 const =/<> ANY/ALL (array_var)，那么我们可以将选择性估计
 * 为这一数组包含运算符，
 * array_var op ARRAY[const]。
 *
 * scalararraysel() 已经验证了 ScalarArrayOpExpr 的运算符
 * 是数组元素类型的默认相等或不相等运算符，并且
 * 已经积极地将两个输入简化为常量。
 *
 * 返回选择性 (0..1)，如果我们无法估计选择性则返回 -1。
 */
Selectivity scalararraysel_containment(PlannerInfo *fc_root,
						   Node *fc_leftop, Node *fc_rightop,
						   Oid fc_elemtype, bool fc_isEquality, bool fc_useOr,
						   int fc_varRelid)
{
	Selectivity fc_selec;
	VariableStatData fc_vardata;
	Datum		fc_constval;
	TypeCacheEntry *fc_typentry;
	FmgrInfo   *fc_cmpfunc;

	/*
	 * rightop 必须是变量，否则放弃。
	 */
	examine_variable(fc_root, fc_rightop, fc_varRelid, &fc_vardata);
	if (!fc_vardata.rel)
	{
		ReleaseVariableStats(fc_vardata);
		return -1.0;
	}

	/*
	 * leftop 必须是常量，否则放弃。
	 */
	if (!IsA(fc_leftop, Const))
	{
		ReleaseVariableStats(fc_vardata);
		return -1.0;
	}
	if (((Const *) fc_leftop)->constisnull)
	{
		/* 如果左侧为 null，qual 无法成功 */
		ReleaseVariableStats(fc_vardata);
		return (Selectivity) 0.0;
	}
	fc_constval = ((Const *) fc_leftop)->constvalue;

	/* 获取元素类型的默认比较函数 */
	fc_typentry = lookup_type_cache(fc_elemtype, TYPECACHE_CMP_PROC_FINFO);
	if (!OidIsValid(fc_typentry->cmp_proc_finfo.fn_oid))
	{
		ReleaseVariableStats(fc_vardata);
		return -1.0;
	}
	fc_cmpfunc = &fc_typentry->cmp_proc_finfo;

	/*
	 * 如果运算符是 <>, 交换 ANY/ALL，然后稍后反转结果。
	 */
	if (!fc_isEquality)
		fc_useOr = !fc_useOr;

	/* 如果可用，获取变量的数组元素统计 */
	if (HeapTupleIsValid(fc_vardata.statsTuple) &&
		statistic_proc_security_check(&fc_vardata, fc_cmpfunc->fn_oid))
	{
		Form_pg_statistic fc_stats;
		AttStatsSlot fc_sslot;
		AttStatsSlot fc_hslot;

		fc_stats = (Form_pg_statistic) GETSTRUCT(fc_vardata.statsTuple);

		/* MCELEM 将是与元素相同类型的数组 */
		if (get_attstatsslot(&fc_sslot, fc_vardata.statsTuple,
							 STATISTIC_KIND_MCELEM, InvalidOid,
							 ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS))
		{
			/* 对于 ALL 情况，还获取不同元素计数的直方图 */
			if (fc_useOr ||
				!get_attstatsslot(&fc_hslot, fc_vardata.statsTuple,
								  STATISTIC_KIND_DECHIST, InvalidOid,
								  ATTSTATSSLOT_NUMBERS))
				memset(&fc_hslot, 0, sizeof(fc_hslot));

			/*
			 * 对于 = ANY，估算为 var @> ARRAY[const]。
			 *
			 * 对于 = ALL，估算为 var <@ ARRAY[const]。
			 */
			if (fc_useOr)
				fc_selec = fc_mcelem_array_contain_overlap_selec(fc_sslot.values,
														   fc_sslot.nvalues,
														   fc_sslot.numbers,
														   fc_sslot.nnumbers,
														   &fc_constval, 1,
														   OID_ARRAY_CONTAINS_OP,
														   fc_typentry);
			else
				fc_selec = fc_mcelem_array_contained_selec(fc_sslot.values,
													 fc_sslot.nvalues,
													 fc_sslot.numbers,
													 fc_sslot.nnumbers,
													 &fc_constval, 1,
													 fc_hslot.numbers,
													 fc_hslot.nnumbers,
													 OID_ARRAY_CONTAINED_OP,
													 fc_typentry);

			free_attstatsslot(&fc_hslot);
			free_attstatsslot(&fc_sslot);
		}
		else
		{
			/* 没有最常见元素信息，因此不使用 */
			if (fc_useOr)
				fc_selec = fc_mcelem_array_contain_overlap_selec(NULL, 0,
														   NULL, 0,
														   &fc_constval, 1,
														   OID_ARRAY_CONTAINS_OP,
														   fc_typentry);
			else
				fc_selec = fc_mcelem_array_contained_selec(NULL, 0,
													 NULL, 0,
													 &fc_constval, 1,
													 NULL, 0,
													 OID_ARRAY_CONTAINED_OP,
													 fc_typentry);
		}

		/*
		 * MCE统计信息只计算非NULL行，因此要调整NULL行。
		 */
		fc_selec *= (1.0 - fc_stats->stanullfrac);
	}
	else
	{
		/* 完全没有统计信息，因此不使用 */
		if (fc_useOr)
			fc_selec = fc_mcelem_array_contain_overlap_selec(NULL, 0,
													   NULL, 0,
													   &fc_constval, 1,
													   OID_ARRAY_CONTAINS_OP,
													   fc_typentry);
		else
			fc_selec = fc_mcelem_array_contained_selec(NULL, 0,
												 NULL, 0,
												 &fc_constval, 1,
												 NULL, 0,
												 OID_ARRAY_CONTAINED_OP,
												 fc_typentry);
		/* 我们假设这里没有NULL，因此没有stanullfrac校正 */
	}

	ReleaseVariableStats(fc_vardata);

	/*
	 * 如果运算符是 <>, 则颠倒结果。
	 */
	if (!fc_isEquality)
		fc_selec = 1.0 - fc_selec;

	CLAMP_PROBABILITY(fc_selec);

	return fc_selec;
}

/*
 * arraycontsel -- 数组 @>, &&, <@ 运算符的限制选择性
 */
Datum arraycontsel(PG_FUNCTION_ARGS)
{
	PlannerInfo *fc_root = (PlannerInfo *) PG_GETARG_POINTER(0);
	Oid			fc_operator = PG_GETARG_OID(1);
	List	   *fc_args = (List *) PG_GETARG_POINTER(2);
	int			fc_varRelid = PG_GETARG_INT32(3);
	VariableStatData fc_vardata;
	Node	   *fc_other;
	bool		fc_varonleft;
	Selectivity fc_selec;
	Oid			fc_element_typeid;

	/*
	 * 如果表达式不是 (变量 op 某个值) 或 (某个值 op
	 * 变量)，那么返回默认估计。
	 */
	if (!get_restriction_variable(fc_root, fc_args, fc_varRelid,
								  &fc_vardata, &fc_other, &fc_varonleft))
		PG_RETURN_FLOAT8(DEFAULT_SEL(fc_operator));

	/*
	 * 如果 something 也不是常量，就无法做任何有用的事情。
	 */
	if (!IsA(fc_other, Const))
	{
		ReleaseVariableStats(fc_vardata);
		PG_RETURN_FLOAT8(DEFAULT_SEL(fc_operator));
	}

	/*
	 * “&&”、“@>”和“<@”运算符是严格的，因此我们可以立即处理
	 * NULL 常量。
	 */
	if (((Const *) fc_other)->constisnull)
	{
		ReleaseVariableStats(fc_vardata);
		PG_RETURN_FLOAT8(0.0);
	}

	/*
	 * 如果 var 在右侧，则交换运算符，以便我们可以假定 var 在
	 * 接下来的处理过程中在左侧。
	 */
	if (!fc_varonleft)
	{
		if (fc_operator == OID_ARRAY_CONTAINS_OP)
			fc_operator = OID_ARRAY_CONTAINED_OP;
		else if (fc_operator == OID_ARRAY_CONTAINED_OP)
			fc_operator = OID_ARRAY_CONTAINS_OP;
	}

	/*
	 * 好的，这里有一个 Var 和一个 Const。我们需要 Const 是一个
	 * 数组，并且与列具有相同的元素类型，否则我们无法做任何
	 * 有用的事情。（这种情况可能会在运行时失败，但在这里
	 * 我们宁愿返回默认估计。）
	 */
	fc_element_typeid = get_base_element_type(((Const *) fc_other)->consttype);
	if (fc_element_typeid != InvalidOid &&
		fc_element_typeid == get_base_element_type(fc_vardata.vartype))
	{
		fc_selec = fc_calc_arraycontsel(&fc_vardata, ((Const *) fc_other)->constvalue,
								  fc_element_typeid, fc_operator);
	}
	else
	{
		fc_selec = DEFAULT_SEL(fc_operator);
	}

	ReleaseVariableStats(fc_vardata);

	CLAMP_PROBABILITY(fc_selec);

	PG_RETURN_FLOAT8((float8) fc_selec);
}

/*
 * arraycontjoinsel -- 数组 @>, &&, <@ 运算符的连接选择性
 */
Datum arraycontjoinsel(PG_FUNCTION_ARGS)
{
	/* 目前这只是一个存根 */
	Oid			fc_operator = PG_GETARG_OID(1);

	PG_RETURN_FLOAT8(DEFAULT_SEL(fc_operator));
}

/*
 * 根据统计信息计算“arraycolumn @> const”，“arraycolumn && const”
 * 或 “arraycolumn <@ const”的选择性
 *
 * 这个函数主要负责提取将要使用的 pg_statistic 数据；
 * 然后我们将这个问题传递给 mcelem_array_selec()。
 */
static Selectivity fc_calc_arraycontsel(VariableStatData *fc_vardata, Datum fc_constval,
				  Oid fc_elemtype, Oid fc_operator)
{
	Selectivity fc_selec;
	TypeCacheEntry *fc_typentry;
	FmgrInfo   *fc_cmpfunc;
	ArrayType  *fc_array;

	/* 获取元素类型的默认比较函数 */
	fc_typentry = lookup_type_cache(fc_elemtype, TYPECACHE_CMP_PROC_FINFO);
	if (!OidIsValid(fc_typentry->cmp_proc_finfo.fn_oid))
		return DEFAULT_SEL(fc_operator);
	fc_cmpfunc = &fc_typentry->cmp_proc_finfo;

	/*
	 * 调用者确保常量是与相同元素类型的数组，现在获取它
	 */
	fc_array = DatumGetArrayTypeP(fc_constval);

	if (HeapTupleIsValid(fc_vardata->statsTuple) &&
		statistic_proc_security_check(fc_vardata, fc_cmpfunc->fn_oid))
	{
		Form_pg_statistic fc_stats;
		AttStatsSlot fc_sslot;
		AttStatsSlot fc_hslot;

		fc_stats = (Form_pg_statistic) GETSTRUCT(fc_vardata->statsTuple);

		/* MCELEM 将是与列相同类型的数组 */
		if (get_attstatsslot(&fc_sslot, fc_vardata->statsTuple,
							 STATISTIC_KIND_MCELEM, InvalidOid,
							 ATTSTATSSLOT_VALUES | ATTSTATSSLOT_NUMBERS))
		{
			/*
			 * 对于“array <@ const”情况，我们还需要不同
			 * 元素计数的直方图。
			 */
			if (fc_operator != OID_ARRAY_CONTAINED_OP ||
				!get_attstatsslot(&fc_hslot, fc_vardata->statsTuple,
								  STATISTIC_KIND_DECHIST, InvalidOid,
								  ATTSTATSSLOT_NUMBERS))
				memset(&fc_hslot, 0, sizeof(fc_hslot));

			/* 使用最常见元素槽来处理数组 Var。 */
			fc_selec = fc_mcelem_array_selec(fc_array, fc_typentry,
									   fc_sslot.values, fc_sslot.nvalues,
									   fc_sslot.numbers, fc_sslot.nnumbers,
									   fc_hslot.numbers, fc_hslot.nnumbers,
									   fc_operator);

			free_attstatsslot(&fc_hslot);
			free_attstatsslot(&fc_sslot);
		}
		else
		{
			/* 没有最常见元素信息，因此不使用 */
			fc_selec = fc_mcelem_array_selec(fc_array, fc_typentry,
									   NULL, 0, NULL, 0, NULL, 0,
									   fc_operator);
		}

		/*
		 * MCE统计信息只计算非NULL行，因此要调整NULL行。
		 */
		fc_selec *= (1.0 - fc_stats->stanullfrac);
	}
	else
	{
		/* 完全没有统计信息，因此不使用 */
		fc_selec = fc_mcelem_array_selec(fc_array, fc_typentry,
								   NULL, 0, NULL, 0, NULL, 0,
								   fc_operator);
		/* 我们假设这里没有NULL，因此没有stanullfrac校正 */
	}

	/* 如果常量被压缩，释放我们所做的副本 */
	if (PointerGetDatum(fc_array) != fc_constval)
		pfree(fc_array);

	return fc_selec;
}

/*
 * 基于最常见元素统计的数组选择性估计
 *
 * 这个函数仅仅解构和排序数组常量的内容，
 * 然后根据运算符将问题传递给 mcelem_array_contain_overlap_selec 或
 * mcelem_array_contained_selec。
 */
static Selectivity fc_mcelem_array_selec(ArrayType *fc_array, TypeCacheEntry *fc_typentry,
				   Datum *fc_mcelem, int fc_nmcelem,
				   float4 *fc_numbers, int fc_nnumbers,
				   float4 *fc_hist, int fc_nhist,
				   Oid fc_operator)
{
	Selectivity fc_selec;
	int			fc_num_elems;
	Datum	   *fc_elem_values;
	bool	   *fc_elem_nulls;
	bool		fc_null_present;
	int			fc_nonnull_nitems;
	int			fc_i;

	/*
	 * 准备常量数组数据以进行排序。排序可以让我们找到唯一
	 * 元素，并与 MCELEM 数组有效地合并。
	 */
	deconstruct_array(fc_array,
					  fc_typentry->type_id,
					  fc_typentry->typlen,
					  fc_typentry->typbyval,
					  fc_typentry->typalign,
					  &fc_elem_values, &fc_elem_nulls, &fc_num_elems);

	/* 消除任何空值元素 */
	fc_nonnull_nitems = 0;
	fc_null_present = false;
	for (fc_i = 0; fc_i < fc_num_elems; fc_i++)
	{
		if (fc_elem_nulls[fc_i])
			fc_null_present = true;
		else
			fc_elem_values[fc_nonnull_nitems++] = fc_elem_values[fc_i];
	}

	/*
	 * 查询“column @> '{anything, null}'”不会匹配任何内容。
	 * 对于另外两个运算符，常量中空值的存在可以被忽略。
	 */
	if (fc_null_present && fc_operator == OID_ARRAY_CONTAINS_OP)
	{
		pfree(fc_elem_values);
		pfree(fc_elem_nulls);
		return (Selectivity) 0.0;
	}

	/* 使用它们的默认比较函数对提取的元素进行排序。 */
	qsort_arg(fc_elem_values, fc_nonnull_nitems, sizeof(Datum),
			  fc_element_compare, fc_typentry);

	/* 根据运算符分隔情况 */
	if (fc_operator == OID_ARRAY_CONTAINS_OP || fc_operator == OID_ARRAY_OVERLAP_OP)
		fc_selec = fc_mcelem_array_contain_overlap_selec(fc_mcelem, fc_nmcelem,
												   fc_numbers, fc_nnumbers,
												   fc_elem_values, fc_nonnull_nitems,
												   fc_operator, fc_typentry);
	else if (fc_operator == OID_ARRAY_CONTAINED_OP)
		fc_selec = fc_mcelem_array_contained_selec(fc_mcelem, fc_nmcelem,
											 fc_numbers, fc_nnumbers,
											 fc_elem_values, fc_nonnull_nitems,
											 fc_hist, fc_nhist,
											 fc_operator, fc_typentry);
	else
	{
		elog(ERROR, "arraycontsel called for unrecognized operator %u",
			 fc_operator);
		fc_selec = 0.0;			/* 保持编译器安静 */
	}

	pfree(fc_elem_values);
	pfree(fc_elem_nulls);
	return fc_selec;
}

/*
 * 根据最常见元素统计估计“column @> const”和“column && const”的
 * 选择性。这个估计假设元素的出现是独立的。
 *
 * mcelem（长度为 nmcelem）和 numbers（长度为 nnumbers）来自
 * 数组列的 MCELEM 统计槽，或者如果没有统计信息，则为 NULL/0。
 * array_data（长度为 nitems）是常量的元素。
 *
 * 假设 mcelem 和 array_data 数组已经按照元素类型的 cmpfunc 预排序。
 * 空元素不存在。
 *
 * TODO: 此估计可能能够通过使用不同元素计数直方图来改进。
 * 例如，除了特殊情况“column @> '{}”外，我们可以将计算出的选择性
 * 乘以列中非空数组的比例。
 */
static Selectivity fc_mcelem_array_contain_overlap_selec(Datum *fc_mcelem, int fc_nmcelem,
								   float4 *fc_numbers, int fc_nnumbers,
								   Datum *fc_array_data, int fc_nitems,
								   Oid fc_operator, TypeCacheEntry *fc_typentry)
{
	Selectivity fc_selec,
				fc_elem_selec;
	int			fc_mcelem_index,
				fc_i;
	bool		fc_use_bsearch;
	float4		fc_minfreq;

	/*
	 * 在数字中应该比值多三个，因为最后三个单元格应该包含
	 * 非空元素中的最小和最大频率，然后是空元素的频率。
	 * 如果不正确则忽略这些数字。
	 */
	if (fc_nnumbers != fc_nmcelem + 3)
	{
		fc_numbers = NULL;
		fc_nnumbers = 0;
	}

	if (fc_numbers)
	{
		/* 获取观察到的最低频率 */
		fc_minfreq = fc_numbers[fc_nmcelem];
	}
	else
	{
		/* 没有统计数据则做一些默认假设 */
		fc_minfreq = 2 * (float4) DEFAULT_CONTAIN_SEL;
	}

	/* 决定使用二分搜索是否更快。 */
	if (fc_nitems * fc_floor_log2((uint32) fc_nmcelem) < fc_nmcelem + fc_nitems)
		fc_use_bsearch = true;
	else
		fc_use_bsearch = false;

	if (fc_operator == OID_ARRAY_CONTAINS_OP)
	{
		/*
		 * “column @> const”查询的初始选择性为 1.0，
		 * 并且随着常量数组中每个元素的加入而减少。
		 */
		fc_selec = 1.0;
	}
	else
	{
		/*
		 * “column && const”查询的初始选择性为 0.0，
		 * 并且随着常量数组中每个元素的加入而增加。
		 */
		fc_selec = 0.0;
	}

	/* 并行扫描 mcelem 和数组。 */
	fc_mcelem_index = 0;
	for (fc_i = 0; fc_i < fc_nitems; fc_i++)
	{
		bool		fc_match = false;

		/* 忽略数组数据中的任何重复项。 */
		if (fc_i > 0 &&
			fc_element_compare(&fc_array_data[fc_i - 1], &fc_array_data[fc_i], fc_typentry) == 0)
			continue;

		/* 找到最小的 MCELEM >= 此数组项。 */
		if (fc_use_bsearch)
		{
			fc_match = fc_find_next_mcelem(fc_mcelem, fc_nmcelem, fc_array_data[fc_i],
									 &fc_mcelem_index, fc_typentry);
		}
		else
		{
			while (fc_mcelem_index < fc_nmcelem)
			{
				int			fc_cmp = fc_element_compare(&fc_mcelem[fc_mcelem_index],
												  &fc_array_data[fc_i],
												  fc_typentry);

				if (fc_cmp < 0)
					fc_mcelem_index++;
				else
				{
					if (fc_cmp == 0)
						fc_match = true;	/* mcelem 被找到 */
					break;
				}
			}
		}

		if (fc_match && fc_numbers)
		{
			/* MCELEM 匹配数组项；使用其频率。 */
			fc_elem_selec = fc_numbers[fc_mcelem_index];
			fc_mcelem_index++;
		}
		else
		{
			/*
			 * 元素不在 MCELEM 中。返回默认，但假设
			 * 选择性不超过 minfreq / 2。
			 */
			fc_elem_selec = Min(DEFAULT_CONTAIN_SEL, fc_minfreq / 2);
		}

		/*
		 * 使用当前元素的选择性和元素出现独立性的假设更新整体选择性。
		 */
		if (fc_operator == OID_ARRAY_CONTAINS_OP)
			fc_selec *= fc_elem_selec;
		else
			fc_selec = fc_selec + fc_elem_selec - fc_selec * fc_elem_selec;

		/* 将中间结果限制在合理范围内，以避免舍入误差 */
		CLAMP_PROBABILITY(fc_selec);
	}

	return fc_selec;
}

/*
 * 基于最常见元素统计，估计“column <@ const”的选择性。
 *
 * mcelem（长度为nmcelem）和numbers（长度为nnumbers）来自
 * 数组列的MCELEM统计槽，或者如果统计不可用则为NULL/0。
 * array_data（长度为nitems）是常量的元素。
 * hist（长度为nhist）来自数组列的DECHIST统计槽，
 * 或者如果那些统计不可用则为NULL/0。
 *
 * 假定mcelem和array_data数组根据元素类型的cmpfunc预排序。
 * 空元素不存在。
 *
 * 元素的独立出现意味着在匹配行之间存在特定的不同元素计数分布。
 * 实际数据通常会使这个假设不成立。例如，在一个包含元素范围为[0..10]
 * 的11元素整数数组中，元素出现通常不是独立的。如果是，足够大的集合
 * 将包含所有从0到11的不同元素计数。我们使用不同元素计数的直方图来
 * 进行纠正。
 *
 * 在“column @> const”和“column && const”的情况下，
 * 我们通常有一个元素数量较少的“const”（否则我们选择性接近
 * 0或1）。这就是为什么与不同元素计数分布相关的依赖效应在这里
 * 微不足道的原因。在“column <@ const”情况下，元素数量通常较高
 * （否则我们选择性接近0）。这就是为什么我们在这里应该进行
 * 不同元素计数分布的修正。
 *
 * 使用不同元素计数的直方图产生的分布规律与元素的独立出现
 * 的分布规律不同。这个分布规律可以描述如下：
 *
 * P(o1, o2, ..., on) = f1^o1 * (1 - f1)^(1 - o1) * f2^o2 *
 *	  (1 - f2)^(1 - o2) * ... * fn^on * (1 - fn)^(1 - on) * hist[m] / ind[m]
 *
 * 其中：
 * o1, o2, ..., on - 元素1, 2, ..., n的出现次数
 *		（出现次数为1，未出现次数为0）在行中
 * f1, f2, ..., fn - 元素1, 2, ..., n的频率
 *		（根据收集的统计数据中的标量值在[0..1]范围内）
 * m = o1 + o2 + ... + on = 行中的不同元素总数
 * hist[m] - m个元素出现的直方图数据。
 * ind[m] - 假设它们的概率与数组元素的频率相等时，m次出现的概率。
 *
 * ind[m] = sum(f1^o1 * (1 - f1)^(1 - o1) * f2^o2 * (1 - f2)^(1 - o2) *
 * ... * fn^on * (1 - fn)^(1 - on), o1, o2, ..., on) | o1 + o2 + .. on = m
 */
static Selectivity fc_mcelem_array_contained_selec(Datum *fc_mcelem, int fc_nmcelem,
							 float4 *fc_numbers, int fc_nnumbers,
							 Datum *fc_array_data, int fc_nitems,
							 float4 *fc_hist, int fc_nhist,
							 Oid fc_operator, TypeCacheEntry *fc_typentry)
{
	int			fc_mcelem_index,
				fc_i,
				fc_unique_nitems = 0;
	float		fc_selec,
				fc_minfreq,
				fc_nullelem_freq;
	float	   *fc_dist,
			   *fc_mcelem_dist,
			   *fc_hist_part;
	float		fc_avg_count,
				fc_mult,
				fc_rest;
	float	   *fc_elem_selec;

	/*
	 * 在MCELEM槽中，数字的数量应该比值的数量多三个，
	 * 因为最后三个单元格应该保存非空元素之间的最小和最大
	 * 频率，以及空元素的频率。如果不对，就放弃，因为没有
	 * 元素频率我们无法做太多。
	 */
	if (fc_numbers == NULL || fc_nnumbers != fc_nmcelem + 3)
		return DEFAULT_CONTAIN_SEL;

	/* 没有计数直方图也做不了太多 */
	if (fc_hist == NULL || fc_nhist < 3)
		return DEFAULT_CONTAIN_SEL;

	/*
	 * 获取compute_array_stats()存储的一些摘要统计信息：
	 * 最低频率、空元素频率和平均不同元素计数。
	 */
	fc_minfreq = fc_numbers[fc_nmcelem];
	fc_nullelem_freq = fc_numbers[fc_nmcelem + 2];
	fc_avg_count = fc_hist[fc_nhist - 1];

	/*
	 * “rest”将是所有未在MCELEM中表示的元素的频率之和。
	 * 平均不同元素计数是*所有*元素频率的总和。从这一点开始；
	 * 我们将继续减去MCELEM的频率。
	 */
	fc_rest = fc_avg_count;

	/*
	 * mult是一个乘数，表示对每个不在常量中出现的mcelem的概率的估计。
	 */
	fc_mult = 1.0f;

	/*
	 * elem_selec是常量中元素的估计频率数组。
	 */
	fc_elem_selec = (float *) palloc(sizeof(float) * fc_nitems);

	/* 并行扫描 mcelem 和数组。 */
	fc_mcelem_index = 0;
	for (fc_i = 0; fc_i < fc_nitems; fc_i++)
	{
		bool		fc_match = false;

		/* 忽略数组数据中的任何重复项。 */
		if (fc_i > 0 &&
			fc_element_compare(&fc_array_data[fc_i - 1], &fc_array_data[fc_i], fc_typentry) == 0)
			continue;

		/*
		 * 在MCELEM上迭代，直到找到一个大于或等于常量的此元素的条目。
		 * 对跳过的mcelem条目更新“rest”和“mult”。
		 */
		while (fc_mcelem_index < fc_nmcelem)
		{
			int			fc_cmp = fc_element_compare(&fc_mcelem[fc_mcelem_index],
											  &fc_array_data[fc_i],
											  fc_typentry);

			if (fc_cmp < 0)
			{
				fc_mult *= (1.0f - fc_numbers[fc_mcelem_index]);
				fc_rest -= fc_numbers[fc_mcelem_index];
				fc_mcelem_index++;
			}
			else
			{
				if (fc_cmp == 0)
					fc_match = true;	/* mcelem 被找到 */
				break;
			}
		}

		if (fc_match)
		{
			/* MCELEM 匹配数组项。 */
			fc_elem_selec[fc_unique_nitems] = fc_numbers[fc_mcelem_index];
			/* “rest”对于所有mcelems递减，无论是否匹配 */
			fc_rest -= fc_numbers[fc_mcelem_index];
			fc_mcelem_index++;
		}
		else
		{
			/*
			 * 元素不在 MCELEM 中。返回默认，但假设
			 * 选择性不超过 minfreq / 2。
			 */
			fc_elem_selec[fc_unique_nitems] = Min(DEFAULT_CONTAIN_SEL,
											fc_minfreq / 2);
		}

		fc_unique_nitems++;
	}

	
/*
	 * 如果我们在没有耗尽 MCELEM 数组的情况下处理了所有常量元素，完成遍历以完成“rest”和“mult”的计算。
	 */
	while (fc_mcelem_index < fc_nmcelem)
	{
		fc_mult *= (1.0f - fc_numbers[fc_mcelem_index]);
		fc_rest -= fc_numbers[fc_mcelem_index];
		fc_mcelem_index++;
	}

	/*
	 * 许多不同稀有元素的存在实质性降低了选择性。使用泊松分布来估计列值具有零个此类元素的概率。请参见上面的“rest”定义。
	 */
	fc_mult *= exp(-fc_rest);

	/*----------
	 * 使用不同元素计数直方图需要
	 *		O(unique_nitems * (nmcelem + unique_nitems))
	 * 操作。在某个计算成本阈值以上，合理地牺牲精度以减少规划时间。我们将操作数量限制为 EFFORT * nmcelem；由于 nmcelem 受到列统计目标的限制，因此所做的工作是用户可控的。
	 *
	 * 如果操作数量过大，我们可以通过减少 unique_nitems 并仅考虑常量数组中最常见的元素来减少它，而不会失去所有准确性。为了使结果与仅使用那些元素开始时获得的结果完全一致，我们必须从“mult”中移除任何被丢弃元素的频率，但因为这只是一个近似值，实际上我们并不在乎。因此，只需对 elem_selec[] 进行快速排序并取出最大的元素即可。（它们将不再与 array_data[] 的元素匹配，但我们并不在意。）
	 *----------
	 */
#define EFFORT 100

	if ((fc_nmcelem + fc_unique_nitems) > 0 &&
		fc_unique_nitems > EFFORT * fc_nmcelem / (fc_nmcelem + fc_unique_nitems))
	{
		/*
		 * 使用二次公式求解最大允许的 N。我们有 A = 1, B = nmcelem, C = - EFFORT * nmcelem。
		 */
		double		fc_b = (double) fc_nmcelem;
		int			fc_n;

		fc_n = (int) ((sqrt(fc_b * fc_b + 4 * EFFORT * fc_b) - fc_b) / 2);

		/* 排序，然后仅取前 n 个元素 */
		qsort(fc_elem_selec, fc_unique_nitems, sizeof(float),
			  fc_float_compare_desc);
		fc_unique_nitems = fc_n;
	}

	/*
	 * 计算 mcelems 和常量元素的每个不同元素计数的概率。在这一点上，假设元素发生是独立的。
	 */
	fc_dist = fc_calc_distr(fc_elem_selec, fc_unique_nitems, fc_unique_nitems, 0.0f);
	fc_mcelem_dist = fc_calc_distr(fc_numbers, fc_nmcelem, fc_unique_nitems, fc_rest);

	/* 忽略 hist[nhist-1]，这是平均值而不是直方图成员 */
	fc_hist_part = fc_calc_hist(fc_hist, fc_nhist - 1, fc_unique_nitems);

	fc_selec = 0.0f;
	for (fc_i = 0; fc_i <= fc_unique_nitems; fc_i++)
	{
		/*
		 * mult * dist[i] / mcelem_dist[i] 给出我们在假设元素发生独立的条件下，distinct element count = i 的情况下被匹配的概率。
		 */
		if (fc_mcelem_dist[fc_i] > 0)
			fc_selec += fc_hist_part[fc_i] * fc_mult * fc_dist[fc_i] / fc_mcelem_dist[fc_i];
	}

	pfree(fc_dist);
	pfree(fc_mcelem_dist);
	pfree(fc_hist_part);
	pfree(fc_elem_selec);

	/* 考虑 NULL 元素的发生。 */
	fc_selec *= (1.0f - fc_nullelem_freq);

	CLAMP_PROBABILITY(fc_selec);

	return fc_selec;
}

/*
 * 从不同元素计数的直方图中计算前 n 个不同元素计数概率。
 *
 * 返回一个 palloc 的 n+1 个条目的数组，其中 array[k] 是元素计数 k 的概率，k 在 [0..n] 范围内。
 *
 * 我们假设边界为 a 和 b 的直方图框给予 (a,b) 中每个值 1 / ((b - a + 1) * (nhist - 1)) 的概率，并且额外的半值给予 a 和 b 本身。
 */
static float *
fc_calc_hist(const float4 *fc_hist, int fc_nhist, int fc_n)
{
	float	   *fc_hist_part;
	int			fc_k,
				fc_i = 0;
	float		fc_prev_interval = 0,
				fc_next_interval;
	float		fc_frac;

	fc_hist_part = (float *) palloc((fc_n + 1) * sizeof(float));

	/*
	 * frac 是直方图值之间每个区间的概率贡献。我们有 nhist - 1 个区间，因此每个区间的贡献将是 1 / (nhist - 1)。
	 */
	fc_frac = 1.0f / ((float) (fc_nhist - 1));

	for (fc_k = 0; fc_k <= fc_n; fc_k++)
	{
		int			fc_count = 0;

		/*
		 * 计算等于 k 的直方图边界。（虽然理论上直方图应该只包含确切的整数，但条目是浮点数，因此在大值中可能会有舍入误差。将任何小数值视为等于下一个更大的 k。）
		 */
		while (fc_i < fc_nhist && fc_hist[fc_i] <= fc_k)
		{
			fc_count++;
			fc_i++;
		}

		if (fc_count > 0)
		{
			/* k 是至少一个直方图框的确切边界。 */
			float		fc_val;

			/* 找到当前直方图值与下一个值之间的长度 */
			if (fc_i < fc_nhist)
				fc_next_interval = fc_hist[fc_i] - fc_hist[fc_i - 1];
			else
				fc_next_interval = 0;

			/*
			 * count - 1 个直方图框独占 k。它们
			 * 总共贡献 (count - 1) * frac 概率。还要考虑两侧的部分直方图框。
			 */
			fc_val = (float) (fc_count - 1);
			if (fc_next_interval > 0)
				fc_val += 0.5f / fc_next_interval;
			if (fc_prev_interval > 0)
				fc_val += 0.5f / fc_prev_interval;
			fc_hist_part[fc_k] = fc_frac * fc_val;

			fc_prev_interval = fc_next_interval;
		}
		else
		{
			/* k 不出现作为一个确切的直方图边界。 */
			if (fc_prev_interval > 0)
				fc_hist_part[fc_k] = fc_frac / fc_prev_interval;
			else
				fc_hist_part[fc_k] = 0.0f;
		}
	}

	return fc_hist_part;
}

/*
 * 考虑 n 个独立事件，概率为 p[]。该函数
 * 计算精确 k 个事件发生的概率，其中 k 在 [0..m] 范围内。
 * 返回一个大小为 m+1 的 palloc 数组。
 *
 * "rest" 是所有低概率事件的概率总和，这些事件未包含在 p 中。
 *
 * 想象一个大小为 (n + 1) x (m + 1) 的矩阵 M。元素 M[i,j] 表示
 * 第一个 i 个事件中恰好发生 j 个事件的概率。显然 M[0,0] = 1。
 * 对于任何常数 j，每次 i 的增量仅在事件发生时增加概率。所以，根据全概率法则：
 *	M[i,j] = M[i - 1, j] * (1 - p[i]) + M[i - 1, j - 1] * p[i]
 *	对于 i > 0, j > 0。
 *	M[i,0] = M[i - 1, 0] * (1 - p[i]) 对于 i > 0。
 */
static float *
fc_calc_distr(const float *fc_p, int fc_n, int fc_m, float fc_rest)
{
	float	   *fc_row,
			   *fc_prev_row,
			   *fc_tmp;
	int			fc_i,
				fc_j;

	/*
	 * 由于我们只返回矩阵的最后一行，并且仅需要
	 * 当前行和上一行进行计算，因此分配两行。
	 */
	fc_row = (float *) palloc((fc_m + 1) * sizeof(float));
	fc_prev_row = (float *) palloc((fc_m + 1) * sizeof(float));

	/* M[0,0] = 1 */
	fc_row[0] = 1.0f;
	for (fc_i = 1; fc_i <= fc_n; fc_i++)
	{
		float		fc_t = fc_p[fc_i - 1];

		/* 交换行 */
		fc_tmp = fc_row;
		fc_row = fc_prev_row;
		fc_prev_row = fc_tmp;

		/* 计算下一行 */
		for (fc_j = 0; fc_j <= fc_i && fc_j <= fc_m; fc_j++)
		{
			float		fc_val = 0.0f;

			if (fc_j < fc_i)
				fc_val += fc_prev_row[fc_j] * (1.0f - fc_t);
			if (fc_j > 0)
				fc_val += fc_prev_row[fc_j - 1] * fc_t;
			fc_row[fc_j] = fc_val;
		}
	}

	/*
	 * 存在许多不同的稀有（不在 "p" 中）元素会实质性
	 * 降低选择性。用泊松分布建模其集体发生。
	 */
	if (fc_rest > DEFAULT_CONTAIN_SEL)
	{
		float		fc_t;

		/* 交换行 */
		fc_tmp = fc_row;
		fc_row = fc_prev_row;
		fc_prev_row = fc_tmp;

		for (fc_i = 0; fc_i <= fc_m; fc_i++)
			fc_row[fc_i] = 0.0f;

		/* 泊松分布在 0 次发生时的值 */
		fc_t = exp(-fc_rest);

		/*
		 * 计算先前计算的分布与泊松分布的卷积。
		 */
		for (fc_i = 0; fc_i <= fc_m; fc_i++)
		{
			for (fc_j = 0; fc_j <= fc_m - fc_i; fc_j++)
				fc_row[fc_j + fc_i] += fc_prev_row[fc_j] * fc_t;

			/* 获取 (i + 1) 次发生的泊松分布值 */
			fc_t *= fc_rest / (float) (fc_i + 1);
		}
	}

	pfree(fc_prev_row);
	return fc_row;
}

/* 快速计算以 2 为底的对数的向下取整值的函数。 */
static int fc_floor_log2(uint32 fc_n)
{
	int			fc_logval = 0;

	if (fc_n == 0)
		return -1;
	if (fc_n >= (1 << 16))
	{
		fc_n >>= 16;
		fc_logval += 16;
	}
	if (fc_n >= (1 << 8))
	{
		fc_n >>= 8;
		fc_logval += 8;
	}
	if (fc_n >= (1 << 4))
	{
		fc_n >>= 4;
		fc_logval += 4;
	}
	if (fc_n >= (1 << 2))
	{
		fc_n >>= 2;
		fc_logval += 2;
	}
	if (fc_n >= (1 << 1))
	{
		fc_logval += 1;
	}
	return fc_logval;
}

/*
 * find_next_mcelem 进行二分查找最常见元素数组，从 *index 开始，
 * 查找第一个大于等于 value 的成员。它将匹配的位置保存到 *index，
 * 如果是精确匹配则返回 true。（注意：我们假设 mcelem 元素是唯一的，因此不能有多个
 * 精确匹配。）
 */
static bool fc_find_next_mcelem(Datum *fc_mcelem, int fc_nmcelem, Datum fc_value, int *fc_index,
				 TypeCacheEntry *fc_typentry)
{
	int			fc_l = *fc_index,
				fc_r = fc_nmcelem - 1,
				fc_i,
				fc_res;

	while (fc_l <= fc_r)
	{
		fc_i = (fc_l + fc_r) / 2;
		fc_res = fc_element_compare(&fc_mcelem[fc_i], &fc_value, fc_typentry);
		if (fc_res == 0)
		{
			*fc_index = fc_i;
			return true;
		}
		else if (fc_res < 0)
			fc_l = fc_i + 1;
		else
			fc_r = fc_i - 1;
	}
	*fc_index = fc_l;
	return false;
}

/*
 * 元素的比较函数。
 *
 * 我们使用元素类型的默认 btree 操作类，以及其默认排序
 * 如果该类型对排序敏感。
 *
 * XXX 考虑使用 SortSupport 基础设施
 */
static int fc_element_compare(const void *fc_key1, const void *fc_key2, void *fc_arg)
{
	Datum		fc_d1 = *((const Datum *) fc_key1);
	Datum		fc_d2 = *((const Datum *) fc_key2);
	TypeCacheEntry *fc_typentry = (TypeCacheEntry *) fc_arg;
	FmgrInfo   *fc_cmpfunc = &fc_typentry->cmp_proc_finfo;
	Datum		fc_c;

	fc_c = FunctionCall2Coll(fc_cmpfunc, fc_typentry->typcollation, fc_d1, fc_d2);
	return DatumGetInt32(fc_c);
}

/*
 * 将浮点数排序为降序的比较函数。
 */
static int fc_float_compare_desc(const void *fc_key1, const void *fc_key2)
{
	float		fc_d1 = *((const float *) fc_key1);
	float		fc_d2 = *((const float *) fc_key2);

	if (fc_d1 > fc_d2)
		return -1;
	else if (fc_d1 < fc_d2)
		return 1;
	else
		return 0;
}
